//
// Created by win10 on 2024/12/4.
//
#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct Node {
    char data;                // 数据域
    struct Node* left;       // 左子节点指针
    struct Node* right;      // 右子节点指针
} Node;

// 创建新节点
Node * createNode(int data) {
    Node * newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 先序遍历
void preorder(Node * T)
{
    // 设置一个出口 ==》 当我们遇到叶子节点
    if (T == NULL)
    {
        return;
    }
    // 输出当前根节点的值 ==》 大树拆分下去 一个个 子树 的根节点
    printf("%c", T->data);
    // 设置递归
    // 遍历左子树
    preorder(T->left);
    // 遍历右子树
    preorder(T->right);
}

// 中序遍历
void inorder(Node * T)
{
    // 设置出口
    if (T == NULL)
        return;
    // 按照优先级 先对左子树进行遍历
    inorder(T->left);
    // 打印无左子树或已遍历左子树的节点
    printf("%c", T->data);
    // 最后遍历右子树
    inorder(T->right);
}

// 后序遍历
void lastorder(Node * T)
{
    // 设置出口
    if (T == NULL)
        return;
    // 按照优先级 先对左子树遍历
    lastorder(T->left);
    // 再对右子树遍历
    lastorder(T->right);
    // 最后输出节点
    printf("%c", T->data);
}

// 求叶子节点个数
int sum;
void getLeafNum(Node * T)
{
    if (T == NULL)
        return;
    // 判断什么是叶子节点 ==》 左右指针均为空的时候，为叶子节点
    if (T->left == NULL && T->right == NULL)
        sum++;
    getLeafNum(T->left);
    getLeafNum(T->right);
}

// 求树的高度
int depthOfTree(Node * T)
{
    int depth = 0;
    int dleft = 0, dright = 0;
    if (T == NULL)
        return 0;
    dleft = depthOfTree(T->left);
    dright = depthOfTree(T->right);
    // 取左右子树高度较高的那个加一并返回
    return 1 + (dleft > dright ? dleft : dright);
}

// 主函数
int main() {
    // 创建节点 并 赋值
    Node * NodeA = createNode('A');
    Node * NodeB = createNode('B');
    Node * NodeD = createNode('D');
    Node * NodeF = createNode('F');
    Node * NodeI = createNode('I');
    Node * NodeL = createNode('L');

    // 存储节点之间的逻辑关系
    NodeA->left = NodeB;
    NodeA->right = NodeD;
    NodeB->right = NodeF;
    NodeF->left = NodeL;
    NodeD->left = NodeI;

    // 遍历
    printf("traversal beginning! ");
    printf("\npreorder:");
    preorder(NodeA);

    printf("\ninorder:");
    inorder(NodeA);

    printf("\nlastorder:");
    lastorder(NodeA);


    return 0;
}
